{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Left Leaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumOfLeftLeaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #左叶子之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉树的根节点&nbsp;<code>root</code>&nbsp;，返回所有左叶子之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/08/leftsum-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [3,9,20,null,null,15,7] \n",
    "<strong>输出:</strong> 24 \n",
    "<strong>解释:</strong> 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1]\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点数在&nbsp;<code>[1, 1000]</code>&nbsp;范围内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-left-leaves](https://leetcode.cn/problems/sum-of-left-leaves/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-left-leaves](https://leetcode.cn/problems/sum-of-left-leaves/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "        queue = [root]\n",
    "        sumval = 0\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                if not node.left.left and not node.left.right:\n",
    "                    sumval += node.left.val\n",
    "                else:\n",
    "                    queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return sumval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        from collections import deque\n",
    "        que = deque([root])\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while que:\n",
    "            num = len(que)\n",
    "            for i in range(num):\n",
    "                node = que.popleft()\n",
    "      \n",
    "                if node.left:\n",
    "                    if not node.left.left and not node.left.right:\n",
    "                        res += node.left.val\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        sum = 0\n",
    "        root_list = collections.deque([root])\n",
    "        while root_list:\n",
    "            tem_node = root_list.popleft()\n",
    "            if tem_node.left:\n",
    "                root_list.append(tem_node.left)\n",
    "                if not (tem_node.left.left or tem_node.left.right):\n",
    "                    sum += tem_node.left.val\n",
    "            if tem_node.right:\n",
    "                root_list.append(tem_node.right)\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        res = 0\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur.left and not cur.left.left and not cur.left.right:\n",
    "                res += cur.left.val\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 使用迭代法\n",
    "        queue = deque([root])\n",
    "        res = 0\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                ele = queue.popleft()\n",
    "                if ele.left:\n",
    "                    queue.append(ele.left)\n",
    "                    if not ele.left.left and not ele.left.right:\n",
    "                        res += ele.left.val\n",
    "                if ele.right:\n",
    "                    queue.append(ele.right)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        deque=collections.deque([root])\n",
    "\n",
    "        res=0\n",
    "\n",
    "        while deque:\n",
    "            for _ in range(len(deque)):\n",
    "                cur=deque.popleft()\n",
    "                if cur.left and not cur.left.left and not cur.left.right:\n",
    "                    res+=cur.left.val\n",
    "                if cur.left:\n",
    "                    deque.append(cur.left)\n",
    "                if cur.right:\n",
    "                    deque.append(cur.right)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        #层序\n",
    "        if not root:\n",
    "            return 0\n",
    "        st = [root]\n",
    "        result = 0\n",
    "        while st:\n",
    "            node = st.pop()\n",
    "            if node.left:\n",
    "                st.append(node.left)\n",
    "            if node.right:\n",
    "                st.append(node.right)\n",
    "            if node.left and node.left.left is None and node.left.right is None:\n",
    "                result += node.left.val\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        #层序\n",
    "        if not root:\n",
    "            return 0\n",
    "        st = [root]\n",
    "        result = 0\n",
    "        while st:\n",
    "            node = st.pop(0)\n",
    "            if node.left:\n",
    "                st.append(node.left)\n",
    "            if node.right:\n",
    "                st.append(node.right)\n",
    "            if node.left and node.left.left is None and node.left.right is None:\n",
    "                result += node.left.val\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        count=0\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack=[]\n",
    "        stack.append(root)\n",
    "        while stack:\n",
    "            cur=stack.pop()\n",
    "            lnode=cur.left\n",
    "            if lnode and not lnode.left and not lnode.right:\n",
    "                count+=lnode.val\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 迭代\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        sum_left_value = 0\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                sum_left_value += node.left.val\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return sum_left_value\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "        results_sum = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                 \n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                    if cur.left.left is None and cur.left.right is None:\n",
    "                        results_sum += cur.left.val\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            \n",
    "        return results_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        que = [root]\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while que:\n",
    "            num = len(que)\n",
    "            for i in range(num):\n",
    "                node = que.pop(0)\n",
    "      \n",
    "                if node.left:\n",
    "                    if not node.left.left and not node.left.right:\n",
    "                        res += node.left.val\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 解题思路：通过父节点判断其左孩子是否是左叶子；不能通过当前结点判断该节点是否是左叶子\n",
    "#          父节点的左孩子不为空，且该左孩子的左孩子与右孩子为空\n",
    "\n",
    "# 递归法：使用后序遍历，因为要通过递归函数的返回值来累加求取左叶子数值之和\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "\n",
    "        leftvalue = self.sumOfLeftLeaves(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            leftvalue = root.left.val\n",
    "\n",
    "        rightvalue = self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        return leftvalue + rightvalue\n",
    "\n",
    "\n",
    "# 迭代法：深度优先遍历，栈实现   \n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        st = []\n",
    "        st.append(root)\n",
    "        leftvalue = 0\n",
    "        while st:\n",
    "            node = st.pop()\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                leftvalue += node.left.val\n",
    "\n",
    "            if node.right:\n",
    "                st.append(node.right)\n",
    "            if node.left:\n",
    "                st.append(node.left)\n",
    "\n",
    "        return leftvalue\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\r\n",
    "        # 用栈迭代法\r\n",
    "        if not root:\r\n",
    "            return 0\r\n",
    "        stack = [root]\r\n",
    "        result = 0\r\n",
    "        while stack:\r\n",
    "            cur = stack.pop()\r\n",
    "            if cur.left and not cur.left.left and not cur.left.right:\r\n",
    "                result += cur.left.val\r\n",
    "            # 前序遍历，先右后左入栈\r\n",
    "            if cur.right:\r\n",
    "                stack.append(cur.right)\r\n",
    "            if cur.left:\r\n",
    "                stack.append(cur.left)\r\n",
    "        return result\r\n",
    " \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res,queue=0,[root]      # 广度优先遍历\n",
    "        while queue:\n",
    "            node=queue.pop(0)\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                res+=node.left.val\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        st = [root]\n",
    "        res = 0\n",
    "        while st:\n",
    "            cur = st.pop()\n",
    "            if cur.left and not cur.left.left and not cur.left.right:\n",
    "                res += cur.left.val\n",
    "\n",
    "            if cur.right:\n",
    "                st.append(cur.right)\n",
    "            if cur.left:\n",
    "                st.append(cur.left)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # iteration(pre-order)\n",
    "        stack = []\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack.append(root)\n",
    "        result = 0\n",
    "        while stack:\n",
    "            temp = stack.pop()\n",
    "            if temp.left and not temp.left.left and not temp.left.right:\n",
    "                result += temp.left.val\n",
    "            if temp.right:\n",
    "                stack.append(temp.right)\n",
    "            if temp.left:\n",
    "                stack.append(temp.left)\n",
    "        return result\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 迭代\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        left_value = 0\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur.left and not cur.left.left and not cur.left.right:\n",
    "                left_value += cur.left.val\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "        return left_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 根节点为空\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        stack = [root] # 根节点入栈\n",
    "        result = 0 # 左叶子节点之和\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop() # 根节点出栈\n",
    "\n",
    "            if node.left and not node.left.left and not node.left.right: # 当前节点的左节点为左叶子节点\n",
    "                result += node.left.val\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "           \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 层序遍历所有节点，并判断是否为左叶子\n",
    "        sum = 0\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                if cur.left:\n",
    "                    if not cur.left.left and not cur.left.right:    # 若左孩子为左叶子\n",
    "                        sum += cur.left.val\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        \n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        sum = 0\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if not node.left and not node.right:\n",
    "                continue\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                sum += node.left.val\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        q = collections.deque([(root, False)])\n",
    "\n",
    "        while q:\n",
    "            node, isLeft = q.popleft()\n",
    "            if isLeft and not node.left and not node.right:\n",
    "                res += node.val\n",
    "                continue\n",
    "            if node.left:\n",
    "                q.append((node.left, True))\n",
    "            if node.right:\n",
    "                q.append((node.right, False))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        stack = []\n",
    "        leftsum = 0\n",
    "        if root:\n",
    "            stack.append(root)\n",
    "        while stack:\n",
    "            node = stack.pop(0)\n",
    "            if node.left:\n",
    "                if node.left.left ==None and node.left.right ==None:\n",
    "\n",
    "                    leftsum +=node.left.val\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "        return leftsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root :\n",
    "            return 0\n",
    "        queue = collections.deque([(root,1)])\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            i = 0\n",
    "            n = len(queue)\n",
    "            while i < n:\n",
    "                node , flag = queue.popleft()\n",
    "                if flag == 0 and not node.left and not node.right:\n",
    "                    ans += node.val\n",
    "                if node.left:\n",
    "                    queue.append((node.left , 0))\n",
    "                if node.right:\n",
    "                    queue.append((node.right , 1))\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "\n",
    "        q = collections.deque([root])\n",
    "\n",
    "        while q:\n",
    "            \n",
    "\n",
    "            for i in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "\n",
    "                if cur.left:\n",
    "                    if not cur.left.left and not cur.left.right:\n",
    "                        res += cur.left.val\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "                \n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        sum = 0\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                sum += node.left.val\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    " \n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = collections.deque([root])\n",
    "        result = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                    if cur.left.left == None and cur.left.right == None:\n",
    "                        result += cur.left.val\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "            \n",
    "        return result\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "\n",
    "        q = [root]\n",
    "\n",
    "        while q:\n",
    "            \n",
    "            cur = q.pop()\n",
    "            \n",
    "            if cur.left and not cur.left.left and not cur.left.right:\n",
    "                res += cur.left.val\n",
    "\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "                \n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        stack = [root]\n",
    "        res = 0\n",
    "        while stack:\n",
    "            len_stack = len(stack)\n",
    "            while len_stack:\n",
    "                node = stack.pop()\n",
    "                len_stack -= 1\n",
    "                if node.left and not node.left.left and not node.left.right:\n",
    "                    res += node.left.val\n",
    "                if node.left: stack.append(node.left)\n",
    "                if node.right: stack.append(node.right)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0 \n",
    "        q = deque([root])\n",
    "        ans = 0\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.left:\n",
    "                if not node.left.left and not node.left.right:\n",
    "                    ans += node.left.val \n",
    "                else:\n",
    "                    q.append(node.left)\n",
    "            if node.right:\n",
    "                if node.right.left or node.right.right:\n",
    "                    q.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # if not root: \n",
    "        #     return 0\n",
    "        # if not root.left and not root.right:\n",
    "        #     return 0\n",
    "        # leftValue=self.sumOfLeftLeaves(root.left)\n",
    "        # if root.left and not root.left.left and not root.left.right:\n",
    "        #     leftValue=root.left.val\n",
    "        # rightValue=self.sumOfLeftLeaves(root.right)\n",
    "        # sum_val= leftValue+rightValue\n",
    "        # return sum_val\n",
    "\n",
    "\n",
    "        # if not root: \n",
    "        #     return 0\n",
    "        # leftValue=0\n",
    "        # if root.left and not root.left.left and not root.left.right:\n",
    "        #     leftValue=root.left.val\n",
    "        # return leftValue+self.sumOfLeftLeaves(root.left)+self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        st=[root]\n",
    "        result=0\n",
    "        while st:\n",
    "            node=st.pop()\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                result+=node.left.val\n",
    "            if node.right: \n",
    "                st.append(node.right)\n",
    "            if node.left:\n",
    "                st.append(node.left)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "\n",
    "        q = collections.deque([root])\n",
    "\n",
    "        while q:\n",
    "            \n",
    "            cur = q.popleft()\n",
    "            \n",
    "            if cur.left and not cur.left.left and not cur.left.right:\n",
    "                res += cur.left.val\n",
    "\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "                \n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "        stack = [root]\n",
    "        res = 0\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                res += node.left.val\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res,queue=0,[root]      # 广度优先遍历\n",
    "        while queue:\n",
    "            node=queue.pop(0)\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                res+=node.left.val\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        isLeafNode = lambda node: not node.left and not node.right\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        que = [root]\n",
    "        ans = 0\n",
    "        while que:\n",
    "            node = que.pop(0)\n",
    "            if node.left:\n",
    "                if isLeafNode(node.left):\n",
    "                    ans += node.left.val\n",
    "                else:\n",
    "                    que.append(node.left)\n",
    "            if node.right and not isLeafNode(node.right):\n",
    "                que.append(node.right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        sum = 0\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [root]\n",
    "\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur.left and not cur.left.left and not cur.left.right:\n",
    "                sum += cur.left.val\n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "        return sum\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 根节点为空\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        stack = [root] # 根节点入栈\n",
    "        result = 0 # 左叶子节点之和\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop() # 根节点出栈\n",
    "\n",
    "            if node.left and not node.left.left and not node.left.right: # 当前节点的左节点为左叶子节点\n",
    "                result += node.left.val\n",
    "            if node.right:  # 左右孩子入栈\n",
    "                stack.append(node.right)\n",
    "            if node.left:  # 左孩子入栈，顺序先左或先右入栈都可以\n",
    "                stack.append(node.left)\n",
    "            \n",
    "           \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.sumN = 0\r\n",
    "        \r\n",
    "    def getSumLeft(self, root):\r\n",
    "        if not root:\r\n",
    "            return\r\n",
    "        \r\n",
    "        if root.left and not (root.left.left or root.left.right):\r\n",
    "            self.sumN += root.left.val\r\n",
    "        \r\n",
    "        self.getSumLeft(root.left)\r\n",
    "        self.getSumLeft(root.right)\r\n",
    "        return\r\n",
    "            \r\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\r\n",
    "        # 递归法\r\n",
    "        # if not root:\r\n",
    "        #     return 0\r\n",
    "        # self.getSumLeft(root)\r\n",
    "        # return self.sumN\r\n",
    "\r\n",
    "        # 迭代法\r\n",
    "        stack = [root]\r\n",
    "        sumN = 0\r\n",
    "        \r\n",
    "        while stack:\r\n",
    "            node = stack.pop()\r\n",
    "            \r\n",
    "            if node.left and not (node.left.left or node.left.right):\r\n",
    "                sumN += node.left.val\r\n",
    "                \r\n",
    "            if node.right:\r\n",
    "                stack.append(node.right)\r\n",
    "            if node.left:\r\n",
    "                stack.append(node.left)\r\n",
    "\r\n",
    "        return sumN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    from collections import deque\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root==None:return 0\n",
    "\n",
    "        res = 0\n",
    "        stack,flags = deque(), deque()\n",
    "        stack.append(root)\n",
    "        flags.append(0)\n",
    "        while stack:\n",
    "            for i in range(len(stack)):\n",
    "                tmp_node = stack.popleft()\n",
    "                tmp_flag = flags.popleft()\n",
    "                \n",
    "                if tmp_flag==1 and (tmp_node.left==None and tmp_node.right==None):\n",
    "                    res+=tmp_node.val\n",
    "                if tmp_node.left!=None:\n",
    "                    stack.append(tmp_node.left)\n",
    "                    flags.append(1)\n",
    "                if tmp_node.right!=None:\n",
    "                    stack.append(tmp_node.right)\n",
    "                    flags.append(0)\n",
    "        return res\n",
    "           \n",
    "\n",
    "        return res-root_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if root.left and not root.left.left and not root.left.right:\n",
    "                ans += root.left.val\n",
    "\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 节点的左孩子是叶子 【9 ，15】\n",
    "        if not root: return 0\n",
    "        leftSum = self.sumOfLeftLeaves(root.left)\n",
    "        rightSum = self.sumOfLeftLeaves(root.right)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            return leftSum + rightSum + root.left.val\n",
    "        else:\n",
    "            return leftSum + rightSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        if not root.left and not root.right: return 0\n",
    "\n",
    "        left_value = self.sumOfLeftLeaves(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            left_value = root.left.val\n",
    "\n",
    "        right_value = self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        return left_value + right_value\n",
    "    #     if not root.left: return 0\n",
    "    #     sum_left = 0\n",
    "    #     return self.traverse(root, sum_left)\n",
    "    \n",
    "    # def traverse(self, cur, sum_left):\n",
    "    #     if not cur: return 0\n",
    "    #     if cur.left: \n",
    "    #         self.traverse(cur.left, sum_left)\n",
    "    #         if not cur.left and not cur.right:\n",
    "    #             sum_left += cur.val\n",
    "    #     if cur.right:\n",
    "    #         self.traverse(cur.right, sum_left)\n",
    "    #     return sum_left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(root, stats):\n",
    "            if root is None:\n",
    "                return \n",
    "            if stats==0 and root.left is None and root.right is None:\n",
    "                self.ans += root.val\n",
    "            dfs(root.left, 0)\n",
    "            dfs(root.right, 1)\n",
    "        dfs(root, 1)\n",
    "        return self.ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def sumOfLeftLeaves(self, root):\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root):    \n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            self.res += root.left.val\n",
    "            \n",
    "        self.sumOfLeftLeaves(root.left)\n",
    "        self.sumOfLeftLeaves(root.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        if root == None: return 0\n",
    "        leftValue = self.sumOfLeftLeaves(root.left) \n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            leftValue = root.left.val\n",
    "\n",
    "        rightValue = self.sumOfLeftLeaves(root.right)\n",
    "        \n",
    "        res = leftValue + rightValue # 中\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = 0\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            left = root.left.val\n",
    "        return left + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0#初始化res\n",
    "        def dfs(node):#定义根节点\n",
    "            if not node:#如果没有根节点的时候直接返回值为none\n",
    "                return None\n",
    "            if node.left and not node.left.left and not node.left.right: # 判断是否为左子节点，是否同时又是叶子节点\n",
    "                self.res += node.left.val #统计结果如果这个叶子节点为父节子节点就满足条件加到最终和里\n",
    "            dfs(node.left)#左节点\n",
    "            dfs(node.right)#右节点\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        if not root: return \n",
    "\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            self.sum += root.left.val\n",
    "\n",
    "        res1 = self.sumOfLeftLeaves(root.left)\n",
    "        res2 = self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        return self.sum\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            if root.left and root.left.left is None and root.left.right is None:\n",
    "                res.append(root.left.val)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def trave(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.left:\n",
    "                if root.left.left is None and root.left.right is None:\n",
    "                    res[0] += root.left.val\n",
    "                else:\n",
    "                    trave(root.left)\n",
    "\n",
    "            trave(root.right)\n",
    "\n",
    "\n",
    "\n",
    "        res = [0]\n",
    "        trave(root)\n",
    "\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if  node is None:#空的\n",
    "                return None\n",
    "            # 判断是否为左子节点，是否同时又是叶子节点\n",
    "            if node.left is not None and  node.left.left is None and  node.left.right is None: \n",
    "                self.res += node.left.val #统计结果\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.s = 0\n",
    "        self.tree(root)\n",
    "        return self.s\n",
    "    def tree(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        if root.left:\n",
    "            self.tree(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            self.s+=root.left.val\n",
    "        if root.right:\n",
    "            self.tree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.left != None and root.left.left == None and root.left.right == None:\n",
    "            self.res += root.left.val\n",
    "        self.sumOfLeftLeaves(root.left)\n",
    "        self.sumOfLeftLeaves(root.right)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        leftValue = 0\n",
    "        if root.left is not None and root.left.left is None and root.left.right is None:\n",
    "            leftValue = root.left.val\n",
    "        return leftValue + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            global s\n",
    "            if root:\n",
    "                if root.left and not root.left.left and not root.left.right:\n",
    "                    s+=root.left.val\n",
    "                dfs(root.right)\n",
    "                dfs(root.left)\n",
    "        global s\n",
    "        s=0\n",
    "        dfs(root)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "        leftValue = self.sumOfLeftLeaves(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "             leftValue = root.left.val\n",
    "        rightValue = self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        return leftValue + rightValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: TreeNode) -> int:\n",
    "        ans = [0]\n",
    "        def dfs(root, isleft):\n",
    "            if isleft and root.left is None and root.right is None:\n",
    "                ans[0]+=root.val\n",
    "            if root.left:\n",
    "                dfs(root.left, True)\n",
    "            if root.right:\n",
    "                dfs(root.right, False)\n",
    "        dfs(root,False)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        left_sum = self.sumOfLeftLeaves(root.left)\n",
    "        right_sum = self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            left_sum = root.left.val\n",
    "        \n",
    "        return left_sum + right_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        count = 0\n",
    "        def dfs(q):\n",
    "            nonlocal count\n",
    "            if q is None:\n",
    "                return\n",
    "            if q.left:\n",
    "                if q.left.left is None and q.left.right is None:\n",
    "                    count += q.left.val\n",
    "\n",
    "            \n",
    "\n",
    "            dfs(q.left)\n",
    "            dfs(q.right)\n",
    "\n",
    "\n",
    "\n",
    "        dfs(root)\n",
    "        return count\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                self.res += node.left.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#   def __init__(self,val,left,right):\n",
    "#           self.val = val\n",
    "#           self.left = left\n",
    "#           self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "                return root.left.val + self.sumOfLeftLeaves(root.right)\n",
    "        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)\n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        # 只有左子节点是叶子节点才计算\n",
    "        curLeftV = 0\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            curLeftV = root.left.val\n",
    "\n",
    "        # 递归查左右子树的左子节点的和\n",
    "        return self.sumOfLeftLeaves(root.right) + self.sumOfLeftLeaves(root.left) + curLeftV\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\r\n",
    "        if not root:\r\n",
    "            return 0\r\n",
    "        leftsum = 0\r\n",
    "        if root.left and not root.left.left and not root.left.right:\r\n",
    "            leftsum = root.left.val\r\n",
    "        return leftsum + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.recur(root)\n",
    "\n",
    "    def recur(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.left is not None and root.left.left is None and root.left.right is None:\n",
    "            # 左节点是叶子结点\n",
    "            left_val = root.left.val\n",
    "            right_val = self.recur(root.right)\n",
    "            return left_val + right_val\n",
    "        return self.recur(root.left) + self.recur(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        left = self.sumOfLeftLeaves(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            left = root.left.val\n",
    "        right = self.sumOfLeftLeaves(root.right)\n",
    "        return left + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.sum = 0\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left and not root.left.left and not root.left.right:\n",
    "                self.sum += root.left.val\n",
    "            recur(root.left)\n",
    "            recur(root.right)\n",
    "        recur(root)\n",
    "        return self.sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "       ## def dfs(node):\n",
    "          #  ans = 0\n",
    "        ##    if node.left:\n",
    "          #      ans += node.left.val if i\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            return root.left.val + self.sumOfLeftLeaves(root.right)\n",
    "        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.left and root.left.left is None and root.left.right is None:\n",
    "            res += root.left.val\n",
    "        return res + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        leftval=0\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            leftval=root.left.val\n",
    "        leftval+=self.sumOfLeftLeaves(root.left)\n",
    "        rightval=self.sumOfLeftLeaves(root.right)\n",
    "        sum=leftval + rightval\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 递归-后序\n",
    "    # 1.计算一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # 2.终止条件\n",
    "        if not root: # 根节点为空\n",
    "            return 0\n",
    "        if not root.left and not root.right:  # 节点的左右子树没有左节点之和\n",
    "            return 0\n",
    "        \n",
    "        # 3.单层递归的逻辑\n",
    "        leftValue = self.sumOfLeftLeaves(root.left) # 左\n",
    "        if root.left and not root.left.left and not root.left.right: # 左节点为左叶子节点\n",
    "            leftValue = root.left.val\n",
    "        rightValue = self.sumOfLeftLeaves(root.right) # 右\n",
    "        sumValue = leftValue + rightValue # 中\n",
    "\n",
    "        return sumValue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\r\n",
    "        if not root:\r\n",
    "            return 0\r\n",
    "        self.sum = 0\r\n",
    "        self.dfs(root)\r\n",
    "        return self.sum\r\n",
    "\r\n",
    "    def dfs(self,root):\r\n",
    "        if root.left:\r\n",
    "            if not root.left.left and not root.left.right:\r\n",
    "                self.sum += root.left.val\r\n",
    "            self.dfs(root.left)\r\n",
    "        if root.right:\r\n",
    "            self.dfs(root.right)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        cur_sum = self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)\n",
    "        \n",
    "        if root.left is not None and root.left.left is None and root.left.right is None:\n",
    "            cur_sum += root.left.val\n",
    "        \n",
    "        return cur_sum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # dfs\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.left and not node.left.left and not node.left.right:\n",
    "                res += node.left.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        # recursion\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.left is None and root.right is None:\n",
    "            return 0\n",
    "        \n",
    "        leftvalue = self.sumOfLeftLeaves(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            leftvalue = root.left.val\n",
    "        rightvalue = self.sumOfLeftLeaves(root.right)\n",
    "\n",
    "        Sum = leftvalue + rightvalue\n",
    "        return Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            # 判断是否为左子节点，是否同时又是叶子节点\n",
    "            if node.left and not node.left.left and not node.left.right: \n",
    "                self.res += node.left.val #统计结果\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.count=0\n",
    "        def sum_leftleaf(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.left and root.left.left is None and root.left.right is None:\n",
    "                self.count+=root.left.val\n",
    "            sum_leftleaf(root.left)\n",
    "            sum_leftleaf(root.right)\n",
    "        sum_leftleaf(root)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        leftval=self.sumOfLeftLeaves(root.left)\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            leftval=root.left.val\n",
    "        rightval=self.sumOfLeftLeaves(root.right)\n",
    "        sum=leftval + rightval\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        sum_val=0\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            sum_val+=root.left.val\n",
    "        left=self.sumOfLeftLeaves(root.left)\n",
    "        right=self.sumOfLeftLeaves(root.right)\n",
    "        return sum_val+left+right\n",
    "                \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        self.count=0\n",
    "        def sum_leftleaf(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.left and root.left.left is None and root.left.right is None:\n",
    "                self.count+=root.left.val\n",
    "            sum_leftleaf(root.left)\n",
    "            sum_leftleaf(root.right)\n",
    "            return self.count\n",
    "        return sum_leftleaf(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "\n",
    "        # q = collections.deque([root])\n",
    "\n",
    "        # while q:\n",
    "            \n",
    "        #     cur = q.popleft()\n",
    "            \n",
    "        #     if cur.left and not cur.left.left and not cur.left.right:\n",
    "        #         res += cur.left.val\n",
    "\n",
    "        #     if cur.left:\n",
    "        #         q.append(cur.left)\n",
    "        #     if cur.right:\n",
    "        #         q.append(cur.right)\n",
    "                \n",
    "                \n",
    "        # return res\n",
    "        \n",
    "        if root.left and not root.left.left and not root.left.right:\n",
    "            res += root.left.val\n",
    "\n",
    "        return res + self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
